package leetcode.code1458;

import leetcode.helper.H;

import java.util.Arrays;

import leetcode.IDebug;

public class Solution implements IDebug {

	public int maxDotProduct(int[] nums1, int[] nums2) {
		int m = nums1.length, n = nums2.length;
		int[][] dp = new int[m + 1][n + 1];
		Arrays.fill(dp[0], -1000000);
		for (int i = 0; i <= m; i++) {
			dp[i][0] = -1000000;
		}
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				dp[i][j] = Math.max(Math.max(dp[i][j - 1], dp[i - 1][j]),
						Math.max(dp[i - 1][j - 1] + nums1[i - 1] * nums2[j - 1], nums1[i - 1] * nums2[j - 1]));
			}
		}
		return dp[m][n];
	}

	@Override
	public void debug4() {
		H.compare(-1, this.maxDotProduct(H.str2array3("[-1,-1]"), H.str2array3("[1,1]")));
		H.compare(19, this.maxDotProduct(H.str2array3("[2,1,-2,5]"), H.str2array3("[3,1,-6]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
